package leetcode;

public class x的平方根 {
    // 暴力法
    public static int violent_test(int x) {
        int result = 0;
        for (int i = 0; i <= x ; i++) {
            if (i*i<=x&&(i+1)*(i+1)>x) {
                result = i;
            }
        }
        return result;
    }

    // 二分法
    public static int binary_test(int x) {
        int start = 0,end = x;
        while (start<=end) {
            int mid = (start+end)/2;
            if (mid*mid==x) {
                return mid;
            }
            if (mid*mid<x) {
                start=mid+1;
            }
            if (mid*mid>x) {
                end=mid-1;
            }
        }
        return end;
    }

    public int mySqrt(int x) {
        if (x<=0) {
            return 0;
        }
        return (int)newton((double)x,x);
    }
    public double newton(double i,int x) {

        double res=(i+x/i)/2;
        if(res==i) return i;
        return newton(res,x);
    }
    public static int newton1(int x) {
        double pre = 0, cur = 1;
        while (Math.abs(pre - cur) >= 0.000001) {
            pre = cur;
            cur = (cur+x/cur)/2;
        }
        return (int) pre;
    }
    public static void main(String[] args) {
        System.out.println(violent_test(20));
        System.out.println(binary_test(20));
        System.out.println(newton1(20));
    }
}
